package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 判断链表是不是回文链表：找中间节点和反转链表的综合应用
 * 回文链表：1221是，12321是，123312不是
 * @Date 2023/3/19 10:47
 */
public class Num234_isPalindrom {
    public boolean isPalindrome(ListNode head) {
        /**
         * 将原链表看作两个子链表，以中间节点为其分开：l1:12, l2:321——>转置123，遍历l1和l2判断是否相等
         * 在两个子链表为null之前，如果找到任意一个不相等的就返回false
         */
        //边界条件：链表为null或者只有一个节点都是true
        if(head == null || head.next == null){
            return true;
        }
        //找出链表的中间节点记作middleNode
        ListNode middleNode = middleNode(head);
        //将从middleNode为头结点的链表进行反转后的头结点记作l2
        ListNode l2 = reverseList(middleNode);
        //将以head为头结点的子链表与l2子链表进行遍历判断
        while (head != null & l2!= null){
            //找反例:判断两个子链表的头结点是否相同
            if(head.val != l2.val){
                return false;
            }
            //移动两个子链表头结点的位置
            head = head.next;
            l2 = l2.next;
        }
        return true;
    }

    // 函数目标：找中间节点
    public ListNode middleNode(ListNode head) {
        // 快慢指针法
        ListNode low = head,fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
    // 函数目标：反转链表
    public ListNode reverseList(ListNode head) {
        // 1.base case
        if(head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode newHead = reverseList(head.next);
        // 拼接当前头结点和转后的子链表
        head.next = null;
        next.next = head;
        return newHead;
    }
}
